package com.company;

/**
 * @author zhf
 * @date 2021/10/12
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 电话号码的组合
 */
public class number {
    public static void main(String[] args) {
        String digits = "2";
        number number = new number();
        List<String> com = number.letterCombinations(digits);
        System.out.println(com);
    }
    public List<String> letterCombinations(String digits) {
        int len = digits.length();
        /*
        用来存放已经遍历的字母组合；
         */
        List<String> combinations = new ArrayList<String>();
        if (len == 0){
            return combinations;
        }
        //使用hush表初始化数字代表的字母；
        Map<Character,String> number = new HashMap<Character, String>(){{
            put('2',"abc");
            put('3',"def");
            put('4',"ghi");
            put('5',"jkl");
            put('6',"mno");
            put('7',"pqrs");
            put('8',"tuv");
            put('9',"wxyz");
        }};

        //从树的祖宗节点开始遍历，index：0；
        back(combinations,number,digits,0,new StringBuffer());
        return combinations;
    }

    /*
    构建多叉树，然后使用树的遍历
     */
    public void back(List<String> combinations, Map<Character, String> number, String digits, int index, StringBuffer combination){
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = number.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                back(combinations, number, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }

}

